import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class BitTree{
    public final static int MAX=40;
    BitTree []elements=new BitTree[MAX];
    int front;
    int rear;
    private  Object data;
    private  BitTree left,right;

    public BitTree() {
    }

    public BitTree(Object data) {
        this.data = data;
        left=right=null;
    }

    public BitTree(Object data, BitTree left, BitTree right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return data.toString();
    }

    //前序遍历
    public void preOrder(BitTree parent){
        if(parent==null){
            return;
        }
        System.out.println(parent.data+" ");
        preOrder(parent.left);
        preOrder(parent.right);
    }

    //中序遍历
    public void inOrder(BitTree parent){
        if(parent==null){
            return;
        }

        inOrder(parent.left);
        System.out.println(parent.data+" ");
        inOrder(parent.right);
    }

    //后序遍历
    public void postOrder(BitTree parent){
        if(parent==null){
            return;
        }

        postOrder(parent.left);
        postOrder(parent.right);
        System.out.println(parent.data+" ");
    }

    //结果返回树的高度
    public int height(){
        int heightOfTree;
        if(this==null){
            return -1;
        }
        int leftHeight=(left==null?0:left.height());
        int rightHeght=(right==null?0:right.height());
        heightOfTree=leftHeight<rightHeght?rightHeght:leftHeight;
        return 1+heightOfTree;
    }

    //返回树的层次
    public int level(Object object){
        int levelInTree;
        if(this==null){
            return -1;
        }
        if(object==data){
            return 1;
        }
        int leftLevel=(left==null?-1:left.level(object));
        int rightLevel=(right==null?-1:right.level(object));
        if(leftLevel<0&&rightLevel<0){
            return -1;
        }
        levelInTree=leftLevel<rightLevel?rightLevel:leftLevel;
        return 1+levelInTree;
    }

    //二叉树的叶子树
    public int leafCount(){
        int leafCount=0;
        if(this==null){
            return 0;
        }

        int leftCount=(left==null?0:left.leafCount()+1);
        int rightCount=(right==null?0:right.leafCount()+1);
        leafCount=leftCount+rightCount;
        return leafCount;
    }

    public static void main(String[] args){

        BitTree e=new BitTree("E",null,null);
        BitTree g=new BitTree("G",null,null);
        BitTree f=new BitTree("F",null,null);
        BitTree c=new BitTree("C",f,null);
        BitTree d=new BitTree("D",null,g);
        BitTree b=new BitTree("B",d,e);
        BitTree tree=new BitTree("A",b,c);



        System.out.println("前序遍历二叉树结果: ");
        tree.preOrder(tree);
        System.out.println();
        System.out.println("中序遍历二叉树结果: ");
        tree.inOrder(tree);
        System.out.println();
        System.out.println("后序遍历二叉树结果: ");
        tree.postOrder(tree);
        System.out.println();

        System.out.println("F所在的层次: "+tree.level("F"));
        System.out.println("这棵二叉树的高度: "+tree.height());
        System.out.println("--------------------------------------");

        System.out.println("树的高度为："+(tree.leafCount()+1));
    }
}


